package 程序员面试金典;

import java.util.ArrayList;

/**
 * 面试题 08.07. 无重复字符串的排列组合
 * 无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。
 *
 * 示例1:
 *
 *  输入：S = "qwe"
 *  输出：["qwe", "qew", "wqe", "weq", "ewq", "eqw"]
 * 示例2:
 *
 *  输入：S = "ab"
 *  输出：["ab", "ba"]
 * 提示:
 *
 * 字符都是英文字母。
 * 字符串长度在[1, 9]之间。
 */
public class T08_07 {

    private boolean[] userd = new boolean[10];
    private ArrayList<String> ans = new ArrayList();
    private StringBuilder stringBuilder = new StringBuilder();

    public String[] permutation(String S) {

        dfs(S);
        String[] result = new String[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            result[i] = ans.get(i);
        }

        return result;

    }

    //深度递归
    public void dfs(String S) {
        if (stringBuilder.length() == S.length()) {
            ans.add(stringBuilder.toString());
            return;
        }
        for (int i = 0; i < S.length(); i++) {
            if (!userd[i]) {
                stringBuilder.append(S.charAt(i));
                userd[i] = true;
                dfs(S);
                stringBuilder.deleteCharAt(stringBuilder.length() - 1);
                userd[i] = false;
            }

        }


    }


}
